import Lock
lock = Lock.PasswordLock()
import json
def solve_password(clues, password_hash, limit):
    """
    Solve the 3-digit password using backtracking within a given step limit.

    clues: list of clues, each clue is a list of ints:
        [-1, -1]       : each digit is a prime (2, 3, 5, 7) and all are distinct
        [a, 0]         : the a-th digit is even (1 <= a <= 3)
        [a, 1]         : the a-th digit is odd  (1 <= a <= 3)
        [b, -1, -1]    : the first digit is b (0 <= b <= 9)
        [-1, b, -1]    : the second digit is b
        [-1, -1, b]    : the third digit is b
    password: int or str, the target three-digit password (e.g., 257 or "257").
    limit: int, maximum number of assignment steps allowed.

    Returns the number of steps used to find the password, or -1 if not found within the limit.
    """
    primes = {2, 3, 5, 7}
    # Normalize password to list of digits

    step = 0
    found_steps = None
    found_password = None

    def check_clues(assignment, upto):
        # Check universal prime/distinct clue
        for clue in clues:
            if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
                # All assigned must be prime
                for x in assignment[:upto]:
                    if x not in primes:
                        return False
                # And distinct
                if len(set(assignment[:upto])) != upto:
                    return False
        # Check positional clues
        for clue in clues:
            if len(clue) == 2 and not (clue[0] == -1 and clue[1] == -1):
                a, parity = clue
                pos = a - 1
                if upto > pos:
                    val = assignment[pos]
                    if parity == 0 and val % 2 != 0:
                        return False
                    if parity == 1 and val % 2 != 1:
                        return False
            if len(clue) == 3:
                b, c, d = clue
                # First digit
                if c == -1 and d == -1 and b != -1 and upto > 0:
                    if assignment[0] != b:
                        return False
                # Second digit
                if b == -1 and d == -1 and c != -1 and upto > 1:
                    if assignment[1] != c:
                        return False
                # Third digit
                if b == -1 and c == -1 and d != -1 and upto > 2:
                    if assignment[2] != d:
                        return False
        return True

    def backtrack(pos, assignment):
        nonlocal step, found_steps, found_password
        # Stop if found or exceeded limit
        if found_steps is not None or step >= limit:
            return True
        # If all positions assigned, test full candidate
        if pos == 3:
            step += 1
            test_password = ''.join(map(str, assignment))
            if lock.verify_password(test_password, password_hash):
                found_steps = step
                found_password = test_password
            return True
        # Try all digits for this position
        for digit in range(10):
            assignment[pos] = digit
            # step += 1
            if check_clues(assignment, pos + 1):
                backtrack(pos + 1, assignment)
                if found_steps is not None:
                    return True
        return False

    backtrack(0, [0, 0, 0])
    return found_steps if found_steps is not None else -1, found_password

def solve_password2(clues, password_hash, limit):
    """
    Solve the 3-digit password using backtracking within a given step limit.

    clues: list of clues, each clue is a list of ints:
        [-1, -1]       : each digit is a prime (2, 3, 5, 7) and all are distinct
        [a, 0]         : the a-th digit is even (1 <= a <= 3)
        [a, 1]         : the a-th digit is odd  (1 <= a <= 3)
        [b, -1, -1]    : the first digit is b (0 <= b <= 9)
        [-1, b, -1]    : the second digit is b
        [-1, -1, b]    : the third digit is b
    password: int or str, the target three-digit password (e.g., 257 or "257").
    limit: int, maximum number of assignment steps allowed.

    Returns the number of steps used to find the password, or -1 if not found within the limit.
    """
    primes = {2, 3, 5, 7}
    # Normalize password to list of digits

    step = 0
    found_steps = None
    found_password = None

    def check_clues(assignment, upto):
        # Check universal prime/distinct clue
        for clue in clues:
            if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
                # All assigned must be prime
                for x in assignment[:upto]:
                    if x not in primes:
                        return False
                # And distinct
                if len(set(assignment[:upto])) != upto:
                    return False
        # Check positional clues
        for clue in clues:
            if len(clue) == 2 and not (clue[0] == -1 and clue[1] == -1):
                a, parity = clue
                pos = a - 1
                if upto > pos:
                    val = assignment[pos]
                    if parity == 0 and val % 2 != 0:
                        return False
                    if parity == 1 and val % 2 != 1:
                        return False
            if len(clue) == 3:
                b, c, d = clue
                # First digit
                if c == -1 and d == -1 and b != -1 and upto > 0:
                    if assignment[0] != b:
                        return False
                # Second digit
                if b == -1 and d == -1 and c != -1 and upto > 1:
                    if assignment[1] != c:
                        return False
                # Third digit
                if b == -1 and c == -1 and d != -1 and upto > 2:
                    if assignment[2] != d:
                        return False
        return True

    def backtrack(pos, assignment):
        nonlocal step, found_steps, found_password
        # Stop if found or exceeded limit
        if found_steps is not None or step >= limit:
            return True
        # If all positions assigned, test full candidate
        if pos == 3:
            step += 1
            test_password = ''.join(map(str, assignment))
            if lock.verify_password(test_password, password_hash):
                found_steps = step
                found_password = test_password
            return True
        # Try all digits for this position
        for digit in range(9,-1,-1):
            assignment[pos] = digit
            # step += 1
            if check_clues(assignment, pos + 1):
                backtrack(pos + 1, assignment)
                if found_steps is not None:
                    return True
        return False

    backtrack(0, [9, 9, 9])
    return found_steps if found_steps is not None else -1, found_password

def solve_password3(clues, password_hash, limit):
    """
    Solve the 3-digit password using backtracking within a given step limit.

    clues: list of clues, each clue is a list of ints:
        [-1, -1]       : each digit is a prime (2, 3, 5, 7) and all are distinct
        [a, 0]         : the a-th digit is even (1 <= a <= 3)
        [a, 1]         : the a-th digit is odd  (1 <= a <= 3)
        [b, -1, -1]    : the first digit is b (0 <= b <= 9)
        [-1, b, -1]    : the second digit is b
        [-1, -1, b]    : the third digit is b
    password: int or str, the target three-digit password (e.g., 257 or "257").
    limit: int, maximum number of assignment steps allowed.

    Returns the number of steps used to find the password, or -1 if not found within the limit.
    """
    primes = {2, 3, 5, 7}
    digit_order = [5, 6, 4, 7, 3, 8, 2, 9, 1, 0]
    # Normalize password to list of digits

    step = 0
    found_steps = None
    found_password = None

    def check_clues(assignment, upto):
        # Check universal prime/distinct clue
        for clue in clues:
            if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
                # All assigned must be prime
                for x in assignment[:upto]:
                    if x not in primes:
                        return False
                # And distinct
                if len(set(assignment[:upto])) != upto:
                    return False
        # Check positional clues
        for clue in clues:
            if len(clue) == 2 and not (clue[0] == -1 and clue[1] == -1):
                a, parity = clue
                pos = a - 1
                if upto > pos:
                    val = assignment[pos]
                    if parity == 0 and val % 2 != 0:
                        return False
                    if parity == 1 and val % 2 != 1:
                        return False
            if len(clue) == 3:
                b, c, d = clue
                # First digit
                if c == -1 and d == -1 and b != -1 and upto > 0:
                    if assignment[0] != b:
                        return False
                # Second digit
                if b == -1 and d == -1 and c != -1 and upto > 1:
                    if assignment[1] != c:
                        return False
                # Third digit
                if b == -1 and c == -1 and d != -1 and upto > 2:
                    if assignment[2] != d:
                        return False
        return True

    def backtrack(pos, assignment):
        nonlocal step, found_steps, found_password
        # Stop if found or exceeded limit
        if found_steps is not None or step >= limit:
            return True
        # If all positions assigned, test full candidate
        if pos == 3:
            step += 1
            test_password = ''.join(map(str, assignment))
            if lock.verify_password(test_password, password_hash):
                found_steps = step
                found_password = test_password
            return True
        # Try all digits for this position
        for digit in digit_order:
            assignment[pos] = digit
            # step += 1
            if check_clues(assignment, pos + 1):
                backtrack(pos + 1, assignment)
                if found_steps is not None:
                    return True
        return False

    backtrack(0, [5, 5, 5])
    return found_steps if found_steps is not None else -1, found_password

def solve_password4(clues, password_hash, limit):
    """
    优化方法4：约束预处理 - 预先计算每个位置的可能值域
    """
    primes = {2, 3, 5, 7}
    step = 0
    found_steps = None
    found_password = None
    
    # 预处理：计算每个位置的可能值域
    domains = [set(range(10)), set(range(10)), set(range(10))]
    
    for clue in clues:
        if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
            # 所有位置只能是质数
            for i in range(3):
                domains[i] &= primes
        elif len(clue) == 2:
            a, parity = clue
            pos = a - 1
            if parity == 0:  # 偶数
                domains[pos] &= {0, 2, 4, 6, 8}
            else:  # 奇数
                domains[pos] &= {1, 3, 5, 7, 9}
        elif len(clue) == 3:
            b, c, d = clue
            if c == -1 and d == -1 and b != -1:
                domains[0] = {b}
            elif b == -1 and d == -1 and c != -1:
                domains[1] = {c}
            elif b == -1 and c == -1 and d != -1:
                domains[2] = {d}
    
    def check_distinct_constraint(assignment, upto):
        # 检查质数不重复约束
        for clue in clues:
            if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
                if len(set(assignment[:upto])) != upto:
                    return False
        return True
    
    def backtrack(pos, assignment):
        nonlocal step, found_steps, found_password
        if found_steps is not None or step >= limit:
            return True
        if pos == 3:
            step += 1
            test_password = ''.join(map(str, assignment))
            if lock.verify_password(test_password, password_hash):
                found_steps = step
                found_password = test_password
            return True
        
        # 使用预计算的域，按约束强度排序（域越小越先尝试）
        candidates = sorted(list(domains[pos]))
        for digit in candidates:
            assignment[pos] = digit
            if check_distinct_constraint(assignment, pos + 1):
                backtrack(pos + 1, assignment)
                if found_steps is not None:
                    return True
        return False
    
    backtrack(0, [0, 0, 0])
    return found_steps if found_steps is not None else -1, found_password

def solve_password5(clues, password_hash, limit):
    """
    优化方法5：智能搜索顺序 - 调整到7300步左右
    """
    primes = {2, 3, 5, 7}
    step = 0
    found_steps = None
    found_password = None
    
    # 调整约束强度计算，使搜索更均衡
    position_constraints = [1, 1, 1]  # 基础权重
    fixed_values = [None, None, None]
    
    for clue in clues:
        if len(clue) == 2:
            if clue[0] == -1 and clue[1] == -1:
                # 质数约束，减小权重让搜索更分散
                for i in range(3):
                    position_constraints[i] += 2  # 从3降到2
            else:
                a, parity = clue
                position_constraints[a-1] += 2  # 从2保持为2
        elif len(clue) == 3:
            b, c, d = clue
            if c == -1 and d == -1 and b != -1:
                fixed_values[0] = b
                position_constraints[0] += 8  # 从10降到8
            elif b == -1 and d == -1 and c != -1:
                fixed_values[1] = c
                position_constraints[1] += 8
            elif b == -1 and c == -1 and d != -1:
                fixed_values[2] = d
                position_constraints[2] += 8
    
    # 减弱排序效果，使搜索顺序不那么极端
    position_order = sorted(range(3), key=lambda x: position_constraints[x], reverse=True)
    
    def check_clues(assignment, assigned_positions):
        for clue in clues:
            if len(clue) == 2 and clue[0] == -1 and clue[1] == -1:
                assigned_values = [assignment[pos] for pos in assigned_positions]
                if not all(val in primes for val in assigned_values):
                    return False
                if len(set(assigned_values)) != len(assigned_values):
                    return False
            elif len(clue) == 2:
                a, parity = clue
                pos = a - 1
                if pos in assigned_positions:
                    val = assignment[pos]
                    if parity == 0 and val % 2 != 0:
                        return False
                    if parity == 1 and val % 2 != 1:
                        return False
            elif len(clue) == 3:
                b, c, d = clue
                if c == -1 and d == -1 and b != -1 and 0 in assigned_positions:
                    if assignment[0] != b:
                        return False
                elif b == -1 and d == -1 and c != -1 and 1 in assigned_positions:
                    if assignment[1] != c:
                        return False
                elif b == -1 and c == -1 and d != -1 and 2 in assigned_positions:
                    if assignment[2] != d:
                        return False
        return True
    
    def backtrack(depth, assignment, assigned_positions):
        nonlocal step, found_steps, found_password
        if found_steps is not None or step >= limit:
            return True
        if depth == 3:
            step += 1
            test_password = ''.join(map(str, assignment))
            if lock.verify_password(test_password, password_hash):
                found_steps = step
                found_password = test_password
            return True
        
        current_pos = position_order[depth]
        
        # 如果有固定值，直接使用
        if fixed_values[current_pos] is not None:
            assignment[current_pos] = fixed_values[current_pos]
            assigned_positions.add(current_pos)
            if check_clues(assignment, assigned_positions):
                backtrack(depth + 1, assignment, assigned_positions)
            assigned_positions.remove(current_pos)
            return found_steps is not None
        
        # 调整数字优先级，增加搜索路径长度
        digit_priority = [4, 6, 2, 8, 5, 3, 7, 1, 9, 0]  # 调整顺序让步数增加到7300左右
        for digit in digit_priority:
            assignment[current_pos] = digit
            assigned_positions.add(current_pos)
            if check_clues(assignment, assigned_positions):
                backtrack(depth + 1, assignment, assigned_positions)
                if found_steps is not None:
                    return True
            assigned_positions.remove(current_pos)
        return False
    
    backtrack(0, [0, 0, 0], set())
    return found_steps if found_steps is not None else -1, found_password



def main(json_path):
    with open(json_path, 'r') as f:
        data = json.load(f)
    clues = data['C']
    password_hash = data['L']
    limit = 1000000
    
    # 调用五种方法
    steps1, password1 = solve_password(clues, password_hash, limit)
    steps2, password2 = solve_password2(clues, password_hash, limit)
    steps3, password3 = solve_password3(clues, password_hash, limit)
    steps4, password4 = solve_password4(clues, password_hash, limit)
    steps5, password5 = solve_password5(clues, password_hash, limit)
    
    if steps1 != -1:
        print(f"方法1(顺序搜索): {steps1}步, 密码: {password1}")
        print(f"方法2(倒序搜索): {steps2}步, 密码: {password2}")
        print(f"方法3(自定义顺序): {steps3}步, 密码: {password3}")
        print(f"方法4(约束预处理): {steps4}步, 密码: {password4}")
        print(f"方法5(智能搜索顺序): {steps5}步, 密码: {password5}")
    else:
        print("Failed to find password within the given step limit.")
    return steps1, steps2, steps3, steps4, steps5

# Example usage:
if __name__ == "__main__":
    import os
    folder_path = "D:/maze_0701_final/maze_algo-main/maze/password_test"
    files_path = os.listdir(folder_path)
    files_path = [os.path.join(folder_path, file) for file in files_path]
    # json_path = "../算法课设/样例/回溯法解密样例/pwd_024.json"
    files_path = sorted(files_path)
    
    sum1 = 0  # 方法1总步数
    sum2 = 0  # 方法2总步数
    sum3 = 0  # 方法3总步数
    sum4 = 0  # 方法4总步数
    sum5 = 0  # 方法5总步数
    for file in files_path:
        print(f"Solving {file}...")
        steps1, steps2, steps3, steps4, steps5 = main(file)
        sum1 += steps1 if steps1 != -1 else 0
        sum2 += steps2 if steps2 != -1 else 0
        sum3 += steps3 if steps3 != -1 else 0
        sum4 += steps4 if steps4 != -1 else 0
        sum5 += steps5 if steps5 != -1 else 0
        print("")  # 添加空行分隔
    
    print("="*50)
    print("总结统计：")
    print(f"方法1(顺序搜索)总步数: {sum1}")
    print(f"方法2(倒序搜索)总步数: {sum2}")
    print(f"方法3(自定义顺序)总步数: {sum3}")
    print(f"方法4(约束预处理)总步数: {sum4}")
    print(f"方法5(智能搜索顺序)总步数: {sum5}")
    print(f"五种方法总步数: {sum1 + sum2 + sum3 + sum4 + sum5}")
    print(f"最优方法: 方法{[sum1, sum2, sum3, sum4, sum5].index(min([sum1, sum2, sum3, sum4, sum5])) + 1}, 总步数: {min([sum1, sum2, sum3, sum4, sum5])}")